%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% Last Modified by Suri on 19-Sept-2010 %%%%%%%%%
%%%%%%% Last Modified by Suri on 01-October-2010 %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% This is "aamas2010_cameraReady.tex" Dec 2010
% This file should be compiled with "aamas2010.cls" July 2010 or "aamas2010_extendedAbstract.cls" Dec 2010
%
% This example file demonstrates the use of the 'aamas2010.cls'
% LaTeX2e document class file. It is for those submitting
% articles to AAMAS 2010 conference. This file is based on
% the sig-alternate.tex example file.
% The 'sig-alternate.cls' file of ACM will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
% than the original style ACM style.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls ) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with AAMAS data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'aamas2010.cls' you don't have control
% from within the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the IFAAMAS Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% These information will be overwritten by fixed AAMAS 2010 information
% in the style files - it is NOT as you are used with ACM style files.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%

% This is the document class for full camera ready papers and extended abstracts respectively

\documentclass{aamas2010_cameraReady}
%\documentclass{aamas2010_extendedAbstract}

% if you are using PDF LaTex and you cannot find a way for producing
% letter, the following explicit settings may help

\pdfpagewidth=8.5truein
\pdfpageheight=11truein

\usepackage{subfigure}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
%\usepackage{amsthm}
%\usepackage{amsmath}
%\usepackage{graphicx}

\numberwithin{equation}{section}
\numberwithin{figure}{section}
%\theoremstyle{plain}
\newtheorem{thm}{Theorem}
 % \theoremstyle{plain}
  \newtheorem{lem}[thm]{Lemma}
 % \theoremstyle{plain}
  \newtheorem{cor}[thm]{Corollary}

\newcommand{\N}{\mbox{\bbb N}}

\newtheorem{theorem}{\bf Theorem}
\newtheorem{definition}{\bf Definition}
\newtheorem{example}{\bf Example}
\newtheorem{conjecture}{\bf Conjecture}

\begin{document}

% In the original styles from ACM, you would have needed to
% add meta-info here. This is not necessary for AAMAS 2010 as
% the complete copyright information is generated by the cls-files.

% For appropriate information about authors and title written in the
% copyright information, you must use these commands. Note that the copyright
% box is not required for the initial submission.

\AuthorsForCitationInfo{Author1, Author2 and Author3}

\TitleForCitationInfo{The title of your paper should be written here}

\title{The Price of Stability in Networks Formed with Local Information}

% AUTHORS


% For initial submission, do not give author names, but the
% tracking number, instead, as the review process is blind.

% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

%\numberofauthors{8} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%

\numberofauthors{3}

%\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
% 1st. author

%\alignauthor
%Ben Trovato\titlenote{Dr.~Trovato insisted his name be first.}\\
%       \affaddr{Institute for Clarity in Documentation}\\
%       \affaddr{1932 Wallamaloo Lane}\\
%       \affaddr{Wallamaloo, New Zealand}\\
%       \email{trovato@corporation.com}
%% 2nd. author
%\alignauthor
%G.K.M. Tobin\titlenote{The secretary disavows any knowledge of this author's actions.}\\
%       \affaddr{Institute for Clarity in Documentation}\\
%       \affaddr{P.O. Box 1212}\\
%       \affaddr{Dublin, Ohio 43017-6221}\\
%       \email{webmaster@marysville-ohio.com}
%% 3rd. author
%\alignauthor Lars Th{\o}rv{\"a}ld\titlenote{This author is the one who did all the really hard work.}\\
%       \affaddr{The Th{\o}rv{\"a}ld Group}\\
%       \affaddr{1 Th{\o}rv{\"a}ld Circle}\\
%       \affaddr{Hekla, Iceland}\\
%       \email{larst@affiliation.org}
%}

%\and  % use '\and' if you need 'another row' of author names

% 4th. author
%\alignauthor Lawrence P. Leipuner\\
%       \affaddr{Brookhaven Laboratories}\\
%       \affaddr{Brookhaven National Lab}\\
%       \affaddr{P.O. Box 5000}\\
%       \email{lleipuner@researchlabs.org}

% 5th. author
%\alignauthor Sean Fogarty\\
%       \affaddr{NASA Ames Research Center}\\
%       \affaddr{Moffett Field}\\
%       \affaddr{California 94035}\\
%       \email{fogartys@amesres.org}

% 6th. author
%\alignauthor Charles Palmer\\
%       \affaddr{Palmer Research Laboratories}\\
%      \affaddr{8600 Datapoint Drive}\\
%       \affaddr{San Antonio, Texas 78229}\\
%       \email{cpalmer@prl.com}

%\and

%% 7th. author
%\alignauthor Lawrence P. Leipuner\\
%       \affaddr{Brookhaven Laboratories}\\
%       \affaddr{Brookhaven National Lab}\\
%       \affaddr{P.O. Box 5000}\\
%       \email{lleipuner@researchlabs.org}

%% 8th. author
%\alignauthor Sean Fogarty\\
%       \affaddr{NASA Ames Research Center}\\
%       \affaddr{Moffett Field}\\
%       \affaddr{California 94035}\\
%       \email{fogartys@amesres.org}

%% 9th. author
%\alignauthor Charles Palmer\\
%       \affaddr{Palmer Research Laboratories}\\
%       \affaddr{8600 Datapoint Drive}\\
%       \affaddr{San Antonio, Texas 78229}\\
%       \email{cpalmer@prl.com}

%}

%% There's nothing stopping you putting the seventh, eighth, etc.
%% author on the opening page (as the 'third row') but we ask,
%% for aesthetic reasons that you place these 'additional authors'
%% in the \additional authors block, viz.
%\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
%email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
%(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
%\date{30 July 1999}
%% Just remember to make sure that the TOTAL number of authors
%% is the number that will appear on the first page PLUS the
%% number that will appear in the \additionalauthors section.

\maketitle

\begin{abstract}
Consider a set of rational and intelligent agents who wish to form
links among themselves for the purpose of routing information or
traffic. Being rational and intelligent, agents form links with
other agents so that their respective utilities are maximized. In
such scenarios, in general, the set of equilibrium network
topologies may appear quite different from the topologies of
centrally enforced optimum (or efficient) networks. In this paper,
we focus on a {\em local network formation game (LNFG)} wherein
the agents are the players and the utility of each agent depends
only on the local information in the network (or the neighborhood
of the agent). In this setting, we study the tradeoffs between
topologies of equilibrium networks and efficient networks. Perhaps
this is the first effort to study the compatibility of equilibrium
versus efficiency in the process of network formation with only
local information. Towards this end, using the proposed LNFG, we
characterize topologies of equilibrium networks and
topologies of efficient networks based on a few classical results
from extremal graph theory. Then we study the price of stability
(ratio of the sum of utilities of agents in a best equilibrium
network to that of an efficient network) in LNFG in order to
reveal the compatibility of equilibrium networks versus
efficient networks. Interestingly, we find that price of stability
is $1$ for almost all values of the parameters in LNFG. Only for a
few values of the parameters in LNFG, we obtain a lower bound of
$\frac{1}{2}$ on price of stability. This indicates that, under
mild conditions, the proposed LNFG produces equilibrium networks
that are efficient as well. Moreover, we have experimentally
studied the dynamics of LNFG and, in this process, we also
validated the analytical predictions of the topologies of
equilibrium networks using LNFG.
\end{abstract}

% Note that the category section should be completed after reference to the ACM Computing Classification Scheme available at
% http://www.acm.org/about/class/1998/.

%\category{H.4}{Information Systems Applications}{Miscellaneous}
\category{G.2.2}{Mathematics of
Computing}{DiscreteMathematics}[graph theory, network problems]
\category{I.2.11}{Computing Methodologies}{Artificial
Intelligence}[distributed artificial intelligence]


%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%General terms should be selected from the following 16 terms: Algorithms, Management, Measurement, Documentation, Performance, Design, Economics, Reliability, Experimentation, Security, Human Factors, Standardization, Languages, Theory, Legal Aspects, Verification.

\terms{Economics, Design}

%Keywords are your own choice of terms you would like the paper to be indexed by.

\keywords{Network design, rationality, agents, pairwise stability,
efficiency, price of stability.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Introduction %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
\label{introduction}

In many network settings, the behavior of the system is driven by
the actions of a large number of autonomous individuals (agents),
each motivated by self-interest and optimizing an individual
objective function. As a consequence of this, the global
performance of such networks, which are the equilibrium outcomes
of decentralized strategic interactions, can be worse than that of
a network that is enforced by a central authority. In the
literature, networks that are enforced by a central authority are
known as efficient networks. Understanding the compatibility
between the equilibrium networks and efficient networks is the
primary focus of research in network formation.

The crux of most of the models for network formation in the
literature \cite{jackson:08}, \cite{goyal:07}, \cite{hummon00},
\cite{doreian06}, \cite{buskens-vanderijt:07},
\cite{goyal-vegaredondo:07}, \cite{kstw:08}, \cite{johnson:00},
\cite{anshelevich:03}, \cite{anshelevich:08}, \cite{fabrikant:03},
\cite{corbo:05}, \cite{galeotti:06}, \cite{jackson-wolinsky:96},
\cite{jackson:02} is the underlying strategic form game
\cite{myerson:91} where the players, strategies, and utilities are
defined as follows: (i) the individual agents are the players,
(ii) the strategy of each agent is a subset of other agents with
which he/she wants to form links, and (iii) the utility of each
agent depends on the structure of the network. By employing
various notions of equilibrium and efficiency, these studies yield
precise predictions on the network topologies that result, if
equilibrium and efficiency are to be satisfied.

Most of the existing work in the literature
\cite{jackson-wolinsky:96}, \cite{jackson:08}, \cite{goyal:07},
\cite{hummon00}, \cite{doreian06}, \cite{goyal-vegaredondo:07},
\cite{johnson:00}, \cite{anshelevich:03}, \cite{anshelevich:08},
\cite{fabrikant:03}, \cite{corbo:05}, \cite{galeotti:06} model the
process of network formation in a decentralized fashion, in the
sense that the agents in the network take autonomous decisions
whether to form/delete links with other agents. At the same time,
these models require that each agent in the network should know
the entire network structure in order to optimize its own utility.
This is very a demanding requirement as, in real life
applications, it is unlikely that any individual knows the entire
network structure. For example, in online social communities such
as LinkedIn, Orkut, Facebook, an individual more often does not
even know who are all the friends of his friends.

Thus, there is a strong need to study the process of network
formation where each individual needs to know only its
neighborhood in order optimize his/her utility. From now on, we
refer this setting as {\em network formation with local
information}. A first step towards this end is the models proposed
by Buskens and van de Rijt \cite{buskens-vanderijt:07} and
Kleinberg et. al. \cite{kstw:08}. To optimize his/her own utility,
the model \cite{buskens-vanderijt:07} requires each individual to
know just its immediate neighborhood and the model \cite{kstw:08}
requires each individual to know its $2$-hop neighborhood (the set
of all individuals that are reachable within two hops). However,
the model \cite{buskens-vanderijt:07} captures only the cost to
nodes, and it ignores various benefits that nodes can derive from
the network. And, the model \cite{kstw:08} does not study the
compatibility of stability and efficiency. To the best of our
knowledge, this is no model in the literature that
\begin{itemize}
\item satisfactorily models the process of network formation with
local information, and

\item systematically studies the compatibility of pairwise stable
networks versus efficient networks in the context of network
formation with local information.
\end{itemize}
In this paper, we attempt to address this research gap and, in
this sense, this paper contributes to the growing literature on
network formation.

In particular, we propose a strategic form game to model the
process of network formation with local information and we call
this game {\em local network formation game} (LNFG). In this game,
the individuals are the players and the utility of each player
depends only on the structure of the neighborhood of that player.
We define the utility of each player such that it takes into
account not only the benefits that arise from routing information
to and from his/her neighbors but also the costs to maintain links
with his/her neighbors. We note that our proposed model is
realistic compared to the models in the literature, as often an
individual does not know who are all the neighbors of his/her
neighbors. Moreover our model assumes that a link forms with the
consent of both the concerned players, as more often social
contacts emerge in this manner. In such situations, an intuitive
choice of the notion of stability is pairwise stability
\cite{jackson-wolinsky:96}. Informally, we call a network pairwise
stable if no player can delete a link to improve its utility and
no pair of players form a link to improve their respective
utilities. Furthermore, we call a network efficient if the sum of
the utilities of agents is maximal. In this framework, our
objective is to investigate the tradeoffs between the topologies
of the pairwise stable networks and that of efficient networks.

Towards this end, we first characterize topologies of both
pairwise stable networks and efficient networks. In this
characterization, we use a few classical results from extremal
graph theory. Then we study the price of stability using LNFG to
reveal the compatibility of pairwise stable networks versus the
efficient networks. The price of stability is the ratio of the sum
of utilities of players in a best pairwise stable network to that
of an efficient network. Here a best pairwise stable network means
a pairwise stable network with maximum sum of utilities of the
players. Interestingly, we find that the price of stability is $1$
for almost all values of the parameters in LNFG. Only for a few
values of the parameters in LNFG, we obtain a lower bound of
$\frac{1}{2}$ on price of stability. This indicates that, for a
large number of parameter configurations, the proposed LNFG
produces equilibrium networks that are efficient. Moreover, we
have experimentally studied the dynamics of LNFG and, in this
process, we also validated the analytical predictions of the
topologies of equilibrium networks using LNFG.

In what follows, we briefly review the relevant literature and
bring out the research gap.

%In this paper, we focus on network formation games with local
%information wherein the utility of each agent depends only the
%structure of its neighborhood. This certainly reduces the burden
%on the agents in the sense that agents individually need not know
%the entire network structure to maximize their respective
%utilities. In fact, in several real-life applications, agents form
%or delete links with others without knowing the entire network
%structure. For example, (a) In buyer-seller networks, the agents
%(buyers or sellers) actually do not know the structure of the
%entire trading network; and (b) In practice, an individual in a
%online social network (such as Orkut, Facebook, LinkedIn, etc.)
%does not even know who are all the friends of his/her friend. Thus
%it is very important to study network formation with only
%local information. We note that there is not much work in the
%literature towards this end (please refer to relevant work for
%more details).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Relevant Work %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\subsection{Relevant Work}
\label{relevant-work}

The are many possible approaches to modeling network formation.
The initial efforts in this line of research dates back to the
seminal work of Aumann and Myerson \cite{aumann:88} where the
authors propose an extensive form game for the formation of a
network in the context of cooperative games with communication
structures. In this game, the links form in a sequential manner.
Though there certain merits as an approach to modeling network
formation, the extensive form makes it difficult to analyze beyond
very simple examples and the ordering of links can have a
non-trivial impact on which networks emerge \cite{jackson:04,
jackson:08}.

Myerson \cite{myerson:91} suggests a strategic form game model for
network formation. In this model, the consent of both the nodes is
required to form a link. Here players are the nodes and the
strategy of each player is to announce which other players they
wish to be connected to. Though this model is simple to analyze
and captures several aspects of network formation, it generally
has a large multiplicity of Nash equilibria.

Due to the simplicity of the strategic form game model proposed by
Myerson \cite{myerson:91}, it has become a popular approach in
literature \cite{jackson:08}, \cite{goyal:07}, \cite{hummon00},
\cite{doreian06}, \cite{buskens-vanderijt:07},
\cite{goyal-vegaredondo:07}, \cite{kstw:08}, \cite{johnson:00},
\cite{anshelevich:03}, \cite{anshelevich:08}, \cite{fabrikant:03},
\cite{corbo:05}, \cite{galeotti:06}, \cite{jackson-wolinsky:96},
\cite{jackson:02}. In what follows, we have only included a
discussion of models that are most relevant to our work. When
there is no confusion, we use the words {\em graph\/} and {\em
network\/} synonymously.

The modeling of strategic formation in a general network setting
was first studied in the seminal work of
\cite{jackson-wolinsky:96}. They basically consider a value
function and an allocation rule model where the value function
defines a value to each network and the allocation rule
distributes this value to the nodes in the network. They
investigate whether efficient networks will form when
self-interested individuals can choose to form links and/or break
links. The authors define two stylized models\footnote{They are
the connections model and the co-authorship model
(\cite{jackson-wolinsky:96}).}. For these models, the authors
observe that for high and low costs the efficient networks are
pairwise stable, but not always for medium level costs. They also
examine the tension between efficiency and stability and derive
various conditions and allocation rules for which efficiency and
pairwise stability are compatible. An important feature their
model does not capture is that of the intermediary benefits that
nodes gain by being intermediaries lying on the paths between
non-neighbor nodes. In particular, they do not capture the
benefits due to structural holes.
%The model that we work with in our paper is inspired by the value
%function - allocation rule but expands the scope of network
%formation research by blending a specific, natural value function
%with a generic allocation rule.


Hummon \cite{hummon00} carries out several interesting
investigations to unravel more specific topologies using a
specific model\footnote{In the context of the symmetric
connections model \cite{jackson-wolinsky:96}.} proposed by
\cite{jackson-wolinsky:96}. Two different agent-based simulation
approaches, the multi-thread model and the discrete event
simulation model, are used in the analysis of \cite{hummon00} to
explore the dynamics of network evolution based on a model
proposed in \cite{jackson-wolinsky:96}. Hummon identifies certain
pairwise stable structures that are more specific than those
anticipated by the formal analysis of \cite{jackson-wolinsky:96}.
Doreian \cite{doreian06} explores the same issue in a systematic
manner and establishes the conditions under which different
pairwise structures are generated.
%More recently, \cite{doreian08a} investigated this phenomenon in a
%broader context and later \cite{doreian08b} presented some
%specific results for the context of structural holes.

Fabrikant et al. \cite{fabrikant:03} study a network creation game
in the context of communication networks where links are generated
by the unilateral actions of players and link costs are one-sided.
The utility of each agent is the sum of the cost to form links and
the distances to the rest of agents in the network.
Later, Corbo and Parkes \cite{corbo:05}
extended this model to the context bilateral network formation
where the consent of both the agents is required to form a link.
The authors \cite{corbo:05} also study the price of anarchy of the
bilateral network formation game and they show that the
worst-case price of anarchy of the bilateral model
is worse than for the unilateral model \cite{fabrikant:03}.

Anshelevich et al. \cite{anshelevich:03, anshelevich:08} study a
cost-sharing network connection game where, given an undirected
graph structure $G$, players have a set of specified terminal
nodes that they wish to be connected in the purchased network
(which is necessarily a subgraph of $G$). In
\cite{anshelevich:08}, the authors study how fair cost allocation
schemes affect the quality of the best Nash equilibrium network.

Goyal and Vega-Redondo \cite{goyal-vegaredondo:07} propose a
non-cooperative game model in which a node $i$ can benefit from
serving as an intermediary between a pair of nodes $x$ and $y$. In
their model, a node $i$ could lie on an arbitrarily long path
between $x$ and $y$. The authors assume, however, that the
benefits from farther nodes are not subject to decay. They also
assume that the benefit of communication between any pair of nodes
is always $1$ unit. This $1$ unit is distributed to the two
communicating nodes and only to certain so called {\em essential
nodes} (\cite{goyal-vegaredondo:07}) on the paths between the two
communicating nodes. In this setting, the authors show that a star
graph is the only non-empty robust equilibrium graph. The authors
also study the implications of capacity constraints in the ability
of individual nodes to form links to other nodes and show that a
cycle network emerges.

The network formation model proposed by Buskens and van de Rijt
\cite{buskens-vanderijt:07} captures the cost to nodes of wasting
resources on redundant length $2$ paths. This model does not
capture the bridging benefits and the authors restrict their
attention to the setting where all edges have the same cost.
%%% What do they exactly do?

Kleinberg et. al. \cite{kstw:08} propose a non-cooperative game
model of network formation that incorporates the intermediary
benefit received by a node by bridging any pair of non-neighbor
nodes separated by a path of length $2$.
%Note that the utility function in this model is based on the
%benefits of bridging length $2$ paths whereas the utility function
%in \cite{buskens-vanderijt:07} depends on the cost of wasting
%effort on redundant length two paths.
In this setting, the authors characterize the structure of stable
networks with {\em Nash equilibrium\/} as the notion of stability.
They propose a polynomial time algorithm for a node to determine
its best response in a given graph as nodes can choose to link to
any subset of other nodes. The authors also show that stable
networks have a rich combinatorial structure. The authors do not
study the compatibility between pairwise stable networks and
efficient networks.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our Results %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Our Contributions}
\label{results}

%From the above discussion on the existing models for network
%formation in the literature, all the models are decentralized in
%the sense that individuals in the network take autonomous
%decisions whether to form/delete links with other individuals.
%However, these models require that each individual should know the
%entire network structure in order to optimize his/her own utility.
%This is very a demanding requirement as, in real life
%applications, it is unlikely that any individual knows the entire
%network structure. For example, in online social communities such
%as LinkedIn, Orkut, Facebook, almost surely nobody in the network
%knows the network structure. A first step towards this line of
%research is the model proposed by Kleinberg et. al. \cite{kstw:08}
%and here each individual should know about its $2$-hop
%neighborhood in order to maximize his/her utility. The model
%\cite{kstw:08} assumes that links form unilaterally and considers
%Nash equilibrium as the notion of stability. However, the authors
%\cite{kstw:08} do not study the compatibility of stability and
%efficiency.
%
%In this paper, we propose a strategic form game model for network
%formation where each individual should know only its neighborhood
%in order maximize his/her utility. From now on, we refer this
%setting as {\em network formation with local information}. Our
%proposed model is more close to real life applications than the
%model \cite{kstw:08}, as often we do not know who are the
%neighbors of our neighbors (for example, we do not even know who
%are all the friends of our friends in online social communities).
%Moreover, our model assumes that any link forms with the consent
%of both the individuals, as it is the typical nature of social
%contacts. In such situations, an intuitive choice of the notion of
%stability is pairwise stability \cite{jackson-wolinsky:96}. To the
%best of our knowledge, this is perhaps the first effort to study
%the compatibility of pairwise stable networks versus efficient
%networks in the context of network formation with local
%information.
The following are the main contributions of this paper:
\begin{itemize}
\item We first propose a non-cooperative game (LNFG) to model
network formation with local information. This model assumes that
any link forms with the consent of both the individuals. The
utility of each agent in LNFG depends on the following facts: (a)
the benefits and the costs associated with the links to immediate
neighbors; and (b) the benefits that arise from bridging pairs of
non-neighbor nodes. In other words, the utility of each node just
depends on its neighborhood.

\item In this setting, we characterize the topologies of pairwise
stable networks. In particular, we show that the cycle network and
the complete bi-partite network are the non-empty pairwise stable
networks. We note that our findings extend the possible topologies
for pairwise stable networks compared to that of other models in
the literature.

\item We then characterize the topologies of efficient networks
with respect to the LNFG. We do this using a few classical
results from extremal graph theory. We show that the complete network
and the Turan network are the only non-empty efficient networks under
appropriate conditions.

\item Next, we study the price of stability (PoS) of LNFG. We show
that PoS is $1$ for many configurations of the parameters and, for
the rest, we show a lower bound of $\frac{1}{2}$ for Pos. This
indicates that, under mild conditions, the proposed LNFG produces
equilibrium networks that are efficient as well.

\item Moreover, we have experimentally studied the dynamics of
LNFG and, in this process, we also validated the analytical
predictions of the topologies of equilibrium networks using LNFG.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Outline %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Outline of The Paper}
\label{out-line}
The rest of the paper is organized as follows. In \text{Section~\ref{utilitymodel}}, we first present the LNFG in formal terms and explain the various components of the game in detail. In \text{Section~\ref{sec:Stability}}, we characterize the structure of \textit{pairwise-stable} networks in LNFG and present few important results in this regard. \text{Section~\ref{sec:Simulations}} examines pairwise-stability in more detail by studying the dynamic process of network formation in LNFG by performing simulations using a custom-built social network simulator that models the LNFG. In Section~\ref{sec:Efficiency}, we explore the subject of efficiency in LNFG and present some interesting results under various cost-benefit parameters. Using the results of Section~\ref{sec:Stability} and Section~\ref{sec:Efficiency}, we evaluate the price of stability values of the LNFG in Section~\ref{POS}. We finally summarize and discuss possible avenues of future work in Section~\ref{conclusion}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LNFG %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{The Local Network Formation Game}
\label{utilitymodel}

We first note that there are possible ways of modeling network
formation with local information. Here we propose to model network
formation with local information using a strategic form game. Let
$N=\{1,2, \ldots, n\}$ be the set of $n \; (\geq 3)$ players in
the network formation game. Here the players are the agents in the
network. A strategy $s_i$ of a player $i$ is any subset of players
with which the player would like to establish links and these
links are formed under mutual consent. Assume that $S_i$ is the
set of strategies of player $i$. Let $s=(s_1, s_2, \ldots, s_n)$
be a profile of strategies of the players. Also let $S$ be the set
of all such strategy profiles. Each strategy profile $s$ leads to
an undirected graph and we represent it by $g(s)$. Let $\Psi(S)$
be the set of all such undirected graphs. When the context is
clear, we use $g$ and $\Psi$ instead of $g(s)$ and $\Psi(S)$
respectively.
%If the strategy profile $s$ is clear from the context, we simply
%the denote the corresponding graph by $g$ rather than $g(s)$.
If players $i$ and $j$ are connected by a link in a graph $g$,
then we say that $(i,j) \in g$, otherwise we say that $(i,j)
\notin g$. If players $x$ and $y$ form a link $(x,y)$ in a graph
$g$, then we represent the new graph by $g \cup \{(x,y)\}$.
Moreover, we assume that players in the network communicate using
shortest paths and this is a standard assumption in the
literature. In the rest the paper, we use the terms players,
nodes, and individuals interchangeably.

{\em Degree of Node:} Let $d_{i}$ be the degree of node $i$ in a
given undirected graph. Since the graph is undirected, $d_i$
represents the number of neighbors of node $i$. Also, let $N_i$ be
the set of $d_i$ neighbors of node $i$.

{\em Costs:} If nodes $i$ and $j$ are connected by a link in a
given undirected graph, then we assume that the link incurs a cost
$c > 0$ to each node. That is, if the degree of node $i$ is $d_i$,
then node $i$ incurs a cost of $cd_i$.

{\em Benefits from Immediate Neighbors:} Assume that $\delta \in
(0,1)$. If nodes $i$ and $j$ are connected by a link in a given
undirected graph, then we assume that node $i$ gains a benefit of
$\delta$. That is, if the degree of node $i$ is $d_i$, then node
$i$ gains a benefit of $\delta d_i$ from its immediate neighbors.

{\em Bridging Benefits:}
%If a pair of non-neighbor nodes
%communicate using a shortest path of length $2$, then we define
%that a benefit of $\delta^{2}$ arises due to this communication.
If two non-neighbor nodes $j$ and $k$ have a shortest path through
node $i$ and nodes $j$ and $k$ communicate using this path, then:
\begin{itemize}
    \item A benefit of $\delta^{2}$ arises due to the communication,
    \item The benefit $\delta^{2}$ is shared among $j$, $k$, and $i$
    in some fashion, and
    \item We denote the share of benefit $\delta^{2}$ that node $i$ gains by
    bridging the communication between $j$ and $k$ by
    $f_{jk}^{i}(\delta^{2})$. We call $f_{jk}^{i}(\delta^{2})$ as bridging
    benefit to node $i$.
\end{itemize}
For the ease of analysis, we assume that the bridging benefits to
node $i$ are uniform. In other words, for some number
$f^{i}(\delta^{2})$, we assume that $f_{jk}^{i}(\delta^{2}) =
f^{i}(\delta^{2})$ for every pair of non-neighbor $j \in N_i$ and
$k \in N_i$.

With the above definitions in place, we define that the utility of
node $i$ depends on the benefits from immediate neighbors, the
costs to maintain links to these immediate neighbors, and the
bridging benefits. The formal definition of the utility of a node
is as follows: $\forall i \in N$,
\begin{equation}
u_i = d_i(\delta - c) + d_i \Biggl(1-\frac{\sigma_i}{{d_i \choose
2}}\Biggr) f^{i}(\delta^2)
\end{equation}
where $\sigma_i$ is the number of links among the neighbours of
node $i$ in the given graph.

There are three well known ways of defining $f^{i}(\delta^2)$
$\forall i \in N$ in the literature: (i) $f^{i}(\delta^2) =
\delta^{2}$, (ii) $f^{i}(\delta^2) = \alpha \delta^{2}$ for some
$0 < \alpha < 1$, and (iii) $f^{i}(\delta^2) = 0$. In the rest of
this paper, we work with $f^{i}(\delta^2) = \delta^{2}$, $\forall
i \in N$. That is, if node $i$ acts as the bridge for the
communication between a pair of its neighbors, then the benefit of
communication $\delta^{2}$ entirely goes to node $i$. For
instance, the same philosophy is used in Kleinberg et. al.
\cite{kstw:08} as well. We note that the analysis that we perform
by setting $f^{i}(\delta^2) = \delta^{2}$ $\forall i \in N$ can be
easily extended to other two variants of $f^{i}(\delta^2)$.

\subsection{The Strategic Form Game}
Based on the above discussion, we can define a strategic form game
$\Gamma = \Bigl(N, (S_i)_{i \in N}, (u_i)_{i�\in N} \Bigr)$ that
models network formation with local information, where
\begin{equation}
u_i = d_i(\delta - c) + d_i \Biggl(1-\frac{\sigma_i}{{d_i \choose
2}}\Biggr) \delta^2, \qquad i \in N.
\end{equation}
We refer to this strategic form game as LNFG. The following
example illustrates these notions in detail.

\begin{example}
Assume that $N=\{1,2,3,4,5,6\}$ is the set of $6$ players. If $S_1
= \{2,3,4,5,6\}$, $S_2 = \{1\}$, $S_3 = \{1\}$, $S_4 = \{1\}$,
$S_5 = \{1\}$, $S_6 = \{1\}$, then the resultant graph $g1$ is the
star graph as shown in Figure \ref{model-illustration}.(i).
\begin{figure}[!hbtp]
\begin{center}
\includegraphics[scale=0.357]{model-illustration.jpg}
\end{center}
\caption{A stylized example \label{model-illustration}}
\end{figure}
The utilities of the players in the star graph are as follows:
$u_1(g1)=5(\delta-c) + 5\delta^{2}$ and $u_2(g1) = u_3(g1) =
u_4(g1) = u_5(g1) = u_6(g1) = (\delta-c)$.

If $S_1 = \{2,3,4,5,6\}$, $S_2 = \{1,3,6\}$, $S_3 = \{1,2,4\}$,
$S_4 = \{1,3,5\}$, $S_5 = \{1,4,6\}$, $S_6 = \{1,2,5\}$, then the
resultant graph $g2$ is the wheel graph as shown in Figure
\ref{model-illustration}.(ii). The utilities of the players in the
wheel graph are as follows: $u_1(g2)=5(\delta-c) +
\frac{5\delta^{2}}{2}$ and $u_2(g2) = u_3(g2) = u_4(g2) = u_5(g2)
= u_6(g2) = 3(\delta-c) + \delta^{2}$.

On similar lines, if $S_1 = \{2,6\}$, $S_2 = \{1,3\}$, $S_3 =
\{2,4\}$, $S_4 = \{3,5\}$, $S_5 = \{4,6\}$, $S_6 = \{1,5\}$, then
the resultant graph $g3$ is the cycle (shared) graph as shown in
Figure \ref{model-illustration}.(iii). The utilities of the
players in the cycle graph are as follows: $u_1(g3) = u_2(g3) =
u_3(g3) = u_4(g3) = u_5(g3) = u_6(g3) = 2(\delta-c) +
2\delta^{2}$.
\end{example}

\section{Structure of Pairwise Stable \\Networks}\label{sec:Stability}

\subsection{Concept of Pairwise Stability}

We now need to define a notion which captures the stability of a network. The definition of a stable graph embodies the idea that players have the discretion to form or sever links. We assume in this work that the formation of a link requires the consent of both parties involved, but severance can be done unilaterally.
We use a prominent network equilibrium concept namely the \textit{pairwise stability} which was first studied by Jackson and Wolinsky~\cite{jackson-wolinsky:96}. 

\begin{definition}[Pairwise-stability]
A graph \text{$G=(V,E)$} is pairwise-stable if 
\begin{itemize}
 \item $\forall (i,j) \in E, u_i(G) \geq u_i(G-(i,j)) \text{ and } \\ \text{$u_j(G) \geq u_j(G-(i,j))$} $
 \item $\forall (i,j) \notin E, \text { if } u_i(G) < u_i(G+(i,j)) \text{ then } \\ u_j(G) > u_j(G+(i,j)) $
\end{itemize}

\end{definition}
By definition, pairwise-stable networks are robust to one-link deviations. Such one-link deviations are either enabled by single players in isolation (in the case of link-severance), or at the coordinated actions of pairs of players (in the case of link-creation). Pairwise-stability is also extensively used for positive purposes due to its computational (relative) simplicity, and to its ability to generate sharp predictions in many contexts (See Jackson~\cite{jackson:2003}).



\subsection{Charactering pairwise-stable networks in LNFG}
We now outline an important issue which occurs during network formation process and come up with a methodology to overcome this issue which leads us to characterizing \textit{most} of the pairwise-stable networks that may emerge in LNFG. 

Starting with some initial network (the null network, for example), the network structure changes with time as various actors in the network add or remove links to their neighbors, so as to maximize their own individual utility from the network. It would be interesting to determine if, in the long run, the network reaches a stable state (an equilibrium or a near-equilibrium state). If the network does reach a stable state, it would be interesting to know the structure (i.e. shape) of the stable network and if this stable network is unique. 

One way of approaching this is to start with the initial network and model the dynamics of the system as a function of time (or an analogous parameter) and analytically study the asymptotic network structure in the limit as time tends to infinity. However, the dynamics of the system can become very complex even in a moderately sized network, making such an approach infeasible. Further, such results would only be valid for those particular initial networks.

Another approach is to analyze the stability of some of the standard networks (complete network, cycle or shared network, star network etc.) under our utility model. It would then mean that if the network reaches any of these standard stable networks, it is guaranteed to not deviate from this network. However, one problem with this approach is that starting from some initial network, we may not reach any of these standard networks. That is, some non-standard networks could be stable and the dynamic network could emerge into one of these non-standard networks. However, as we shall see from the empirical results, this is not such a bad approach. 

The following result establishes pairwise stability characterizations of some standard networks under the proposed utility model.
\begin{theorem}
\label{lem:StabilityConditions}(a) The complete network is pairwise-stable iff $(c-\delta)\leq0$ (b) The shared (cycle) network is pairwise-stable iff $1\leq(c-\delta)/\delta^{2}\leq2$ (c) The null (empty) network is pairwise-stable iff $(\delta-c)\leq0$ (d) The Star network is not pairwise-stable.
\end{theorem}
\begin{proof}
The proof is very similar in all the four cases and is quite easy to derive using the hypothesis and definitions of pairwise-stability. 
\end{proof}

\begin{theorem}
\label{lem:StabilityConditions1}The complete bipartite network is pairwise-stable iff $(\delta-c)\leq\delta^{2}$and
$(c-\delta)\leq\delta^{2}$ 
\end{theorem}

\begin{proof}
% The outline of proof is very similar in all the four cases. For brevity,
% we only prove (d) here:
%%%%%%%%%%%%%%%%%%nrsuri comment begins
\begin{figure}[h]
%
%\begin{minipage}[t]{0.33\columnwidth}%
%\includegraphics[scale=0.33]{Figures/CompleteBipartite}
%
%\vspace{0.1in}
%\centering
%\small
%\text{$(a)$}%
%\end{minipage}%
\begin{minipage}[t]{0.53\columnwidth}%
\includegraphics[scale=0.33]{Figures/CompleteBipartite-ExtraEdge}

\vspace{0.1in}
\centering
\small
\text{$(a)$}%
\end{minipage}%
\begin{minipage}[t]{0.33\columnwidth}%
\includegraphics[scale=0.33]{Figures/CompleteBipartite-EdgeRemoved}

\vspace{0.1in}
\centering
\small
\text{$(b)$}%
\end{minipage}

\caption{$(a)$ After adding a new edge $ij$ $(b)$ After deleting edge $il$\label{fig:complete-bipartite-network-abc}}

\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%nrsuri comment ends
All the nodes in partition $a{}_{1}$ are symmetrical. Similarly,all the nodes in partition $a{}_{2}$ are symmetrical. Let us first consider nodes in partition $a{}_{1}$. In Figure \ref{fig:complete-bipartite-network-abc},the utility of actor $i$ is 
\begin{align}
u_{i}&=a_{2}(\delta-c)+a_{2}\delta^{2}\label{eq:BaseUtility}
\end{align}

Let us now add the edge $(i,j)$ and calculate the new utility of actor
$i$ after addition of edge $(i,j)$. Clearly, $\sigma_{i}=a_{2}$. 
\begin{align}\label{eq:UtilityAfterAddition}
\nonumber s_{i} &=\Biggl(1-\Biggl(\frac{a_{2}}{\binom{a_2+1}{2}}\Biggr)\Biggr) \\
\nonumber&=  \Biggl(\frac{a_{2}-1}{a_{2}+1}\Biggr)\\
u_{i} &= (a_{2}+1)(\delta-c)+(a_{2}+1)\left(\frac{a_{2}-1}{a_{2}+1}\right)\delta^{2}\nonumber \\
&=  (a_{2}+1)(\delta-c)+(a_{2}-1)\delta^{2}
\end{align}
For the complete bipartite network to be stable with respect to addition of a new edge, the utility in Equation~\ref{eq:BaseUtility} should be greater than or equal to the utility in Equation~\ref{eq:UtilityAfterAddition}. That
is,
\[a_{2}(\delta-c)+a_{2}\delta^{2}\geq(a_{2}+1)(\delta-c)+(a_{2}-1)\delta^{2}\]
which on simplification yields
\begin{align}
\delta^{2}\geq(\delta-c)\label{eq:ConditionForStabilityUnderAddition}
\end{align}
It is easy to see that this result holds if we were to add, instead
of the edge from $i$ to $j$, an edge from $i$ to any other actor
in partition $a_{1}$.

Let us now delete the edge $(i,l)$ and calculate the new utility of actor $i$ after deleting edge $(i,l)$. Clearly, $\sigma_{i}=0$. Therefore, $s{}_{i}=1$ and
\begin{align}
u_{i}=(a_{2}-1)(\delta-c)+(a_{2}-1)\delta^{2}\label{eq:UtilityAfterDeletion}
\end{align}
For the complete bipartite network to be stable with respect to deletion of an edge, the utility in Equation~\ref{eq:BaseUtility} should be greater than or equal to the utility in Equation~\ref{eq:UtilityAfterDeletion} i.e.,
\[
a_{2}(\delta-c)+a_{2}\delta^{2}\geq(a_{2}-1)(\delta-c)+(a_{2}-1)\delta^{2}\]
which on simplification yields
\begin{align}
\delta^{2}\geq(c-\delta)\label{eq:ConditionForStabilityUnderDeletion}
\end{align}
Again, it is easy to see that this result holds if we were to delete,
instead of the edge from $i$ to $l$, an edge from $i$ to any other
actor in partition $a_{2}$.

A complete bipartite network is stable iff if it is stable with respect
to both cases of addition of a new edge and deletion of an existing
edge. That is, a complete bipartite network is stable iff inequalities
\ref{eq:ConditionForStabilityUnderAddition} and \ref{eq:ConditionForStabilityUnderDeletion}
simultaneously hold. By symmetry of actors in partition $a{}_{1}$,
this result applies equally well to all other actors in that partition.
A similar argument applies for actors in partition $a{}_{2}$.\end{proof}

\newpage
\begin{theorem}\label{kpartite-result}
The complete k-partite network is pairwise stable if the following two conditions hold simultaneously
\begin{itemize}
 \item[(1)] $\delta = c$ 
 \item[(2)] $a_i=a, \forall k \geq 3, \forall i \in \{ 1,2,...,k\}, a \in \{1,2,...\}$ 
\end{itemize}
where $a_i$ is the number of nodes in each partition of the \text{k-partite} network.
\end{theorem}

\begin{proof}
We start with a k-partite graph, $G$, which satisfies the \textit{(2)}. Consider a node $i$ in $p^{th}$ partition of $G$ where $1\leq p \leq k$. We construct the proof in two steps. First, we shown that addition of a new edge to a node $i$ decreases its utility. Next, we show deletion of an existing edge $(i,j)$ also decreases the utility of node $i$. From these two steps, we conclude that $G$ is pairwise-stable. As before, we denote degree of node $i$ in $G$ as $d_i$. 

\textit{Step 1 (edge addition): } We can see that, in $G$,  the only link that can be added from node $i$ is to a node $j$ in the $p^{th}$ partition.
Let $\overline{G}$ denoted the network obtained after a new link $(i,j)$ is added to $G$. 
Let $u(i)$ denote the utility of node $i$ in $G$. $u_{add}(i)$ denote the utility of node~$i$ in $\overline{G}$. For pairwise-stability, we need 
\begin{multline}
\nonumber u_{add}(i) - u(i) \leq 0 \\
\Rightarrow \nonumber (\delta-c) + (d_i +1) \delta^2 \Biggl( 1 - \frac{\sigma_i^{'}}{\binom{d_i+1}{2}} \Biggr) - d_i\delta^2 \Biggl( 1 - \frac{\sigma_i}{\binom{d_i}{2}} \Biggr) \leq 0
\end{multline}
where $\sigma_i^{'}$ is the number of links among the neighbours of node $i$ in $\overline{G}$ and $\sigma_i$ is the number of links among the neighbours of node $i$ in $G$. 
We see that $\sigma_i^{'} = \sigma_i + d_j = \sigma_i + d_i $. This is because $d_i=d_j$ as both node~$i$ and node~$j$ are in the same partition of $G$. Now,
\begin{align}
\nonumber (\delta-c) + (d_i +1) \delta^2 \Biggl( 1 - \frac{\sigma_i+d_i}{\binom{d_i+1}{2}} \Biggr) - d_i\delta^2 \Biggl( 1 - \frac{\sigma_i}{\binom{d_i}{2}} \Biggr) \leq 0 
\end{align}
Simplifying, 
\begin{align}
\nonumber (\delta-c) + \delta^2 - \delta^2 \Biggl(\frac{2 \sigma_i + 2d_i}{d_i} - \frac{2 \sigma_i}{d_i -1}\Biggr) \leq 0\\
\nonumber \Rightarrow (\delta-c) + \delta^2 - \delta^2 \Biggl(\frac{-2 \sigma_i+2d_i(d_i-1)}{d_i(d_i-1)} \Biggr) \leq 0\\
\nonumber \Rightarrow (\delta-c) - \delta^2 +  \delta^2 \Biggl(\frac{2 \sigma_i}{d_i(d_i-1)}\Biggr) \leq 0
\end{align}
Thus, $G$ is always pairwise-stable with respect to addition of an edge when 
\begin{align}\label{additionedge}
(\delta-c) &\leq 0
\end{align}
as the last term $\Biggl(\displaystyle\frac{2\sigma_i}{d_i(d_i-1)}\Biggr)$ lies in the interval $[0,1]$. 

\textit{Step 2 (edge deletion): } In $G$, the only link of node $i$ that can be deleted is to a node $j$ in the $q^{th}$ partition where $1 \leq q \leq k$ and $p\neq q$. Let $\overline{G}$ denoted the network obtained after the link $(i,j)$ has been deleted from $G$. Let $u(i)$ denote the utility of node $i$ in $G$. $u_{del}(i)$ denote the utility of node $i$ in $\overline{G}$. For pairwise-stability, we need 
\begin{multline}
\nonumber u_{del}(i) - u(i) \leq 0 \\
\Rightarrow \nonumber -(\delta-c) + (d_i -1) \delta^2 \Biggl( 1 - \frac{\sigma_i^{'}}{\binom{d_i-1}{2}} \Biggr) - d_i\delta^2 \Biggl( 1 - \frac{\sigma_i}{\binom{d_i}{2}} \Biggr) \leq 0
\end{multline}
$\sigma_i^{'}$ denotes the number of links among the neighbours of node $i$ in $\overline{G}$. We can see that $\sigma_i^{'} = \sigma_i -d_j + a_i$. Simplifying, 
\begin{align}\label{deletionedge}
-(\delta-c) - \delta^2 + \delta^2 \underbrace{\Bigl(\frac{-2 \sigma_i + 2d_j-2a_i}{d_i-2} + \frac{2 \sigma_i}{d_i -1}\Bigr)}_{expr_1} \leq 0
\end{align}

\textit{Claim:} Under the given conditions of Theorem~\ref{kpartite-result}, in Equation~\ref{deletionedge}, $expr_1 \leq 1$. 

\smallskip \noindent {\textit{Reason:}}{ 
We know that $d_i = \sum_{j\neq i} a_j$ . Now, we derive an expression for $\sigma_i$.
\begin{align}\label{sigmai}
\nonumber \sigma_i &= \binom{d_i}{2} - \sum_{j\neq i} \binom{a_j}{2} \\
\nonumber &= \frac{d_i(d_i-1)}{2} - \frac{1}{2} \Biggl( \sum_{j\neq i} a_j^2 - \sum_{j\neq i} a_j \Biggr) \\
&= \frac{d_i^2 - \sum_{j \neq i} a_j^2}{2} 
\end{align}
Now, we show that $expr_1 \leq 1$. The proof is by contradiction. Suppose $expr_1  > 1$. 
\begin{align}\label{simplify1}
\nonumber \Bigl(\frac{-2 \sigma_i + 2d_j-2a_i}{d_i-2} + \frac{2 \sigma_i}{d_i -1}\Bigr) &> 1 \\
\nonumber 2(d_j-\sigma_i-a_i)(d_i-1) + (2\sigma_i)(d_i-2) &> (d_i-2)(d_i-1)\\
(2d_jd_i-2\sigma_i-2a_id_i-2d_j+2a_i) &> (d_i^2 -3d_i+2)
\end{align}
From condition \textit{(2)} in hypothesis, we have $a_i=1, \forall i$ and $d_i=d_j=(k-1)a$. Also, using Equation~\ref{sigmai} in Equation~\ref{simplify1} and simplifying, we have 
\begin{align}\label{simplify2}
(k+1)a - (k-1)a^2 &>2 \\
\nonumber \Rightarrow (k+1)a &> 2+ (k-1)a^2 > (k-1)a^2 \\ 
\nonumber \Rightarrow a &< \Biggl( \frac{k+1}{k-1}\Biggr)
\end{align}
Let $y(k) = \bigl(\frac{k+1}{k-1}\bigr)$. As we know that the function $y(k)$ is a decreasing function of $k$ (as derivative of $y(k)$ with respect to $k$   is $< 0$ for $k\geq 3$), we can write 
\begin{align}
\nonumber a &< y(2) \Rightarrow a < 3
\end{align}
So, clearly we can conclude that $expr_1 > 1$ for $0< a < 3$ (i.e., $a=2$ and $a=1$) and $expr_1 \leq 1$ for $a \geq 3$.

Now we will examine what happens when $a=1$ and $a=2$ more closely.
Substituting $a = 1$ in Equation~\ref{simplify2} and simplifying, we get $2>2$ which is absurd. Substituting $a = 2$ in Equation~\ref{simplify2} and simplifying, we get $k<2$ which violates the hypothesis that $k \geq 3$. Hence, by the above arguments, \text{$expr_1 \leq 1, \forall a \in \{1,2, ...\}, \forall k \geq 3$}.

\hfill $\Box$}

Now, we have from hypothesis that $\delta=c$. Using this and the above result, Equation~\ref{deletionedge} reduces to 
\begin{align}\label{deletionedge2}
\nonumber - \delta^2 + \delta^2 \underbrace{\Bigl(\frac{-2 \sigma_i + 2d_j-2a_i}{d_i-2} + \frac{2 \sigma_i}{d_i -1}\Bigr)}_{\leq 1} &\leq 0 \\
\Rightarrow u_{del}(i) - u(i) &\leq 0 
\end{align}
Thus, from Equation~\ref{additionedge} and Equation~\ref{deletionedge2}, node $i$ does not have any incentive to add an edge to $G$ or delete an edge from $G$. As node $i$ was chosen arbitrarily from $G$, we have that $G$ is pairwise-stable.
\end{proof}

% \begin{theorem}\label{otherresults_pairwisestability}
% The following results follow directly from Lemma \ref{lem:StabilityConditions}.
% (a) For the case $\delta=c$, complete, null, shared  and complete bipartite
% networks are stable whereas Star networks are unstable.
% (b) For the case $\delta<c$, null networks are stable whereas complete
% and star networks are unstable. Further, shared networks are stable
% iff $1\leq(c-\delta)/\delta^{2}\leq2$; and complete bipartite networks
% are stable iff $(c-\delta)\leq\delta^{2}$ (c) For the case $\delta>c$
% and $(\delta-c)>\delta^{2}$, complete networks are stable whereas
% shared, null, star and complete bipartite networks are unstable. (d)
% For the case $\delta>c$ and $(\delta-c)<\delta^{2}$, complete and
% complete bipartite networks are stable; shared, star and null networks
% are unstable.\label{cor:Expected-Regions-of-Stability}
% \end{theorem}



\begin{table}[h]
\centering
% \begin{minipage}{9cm}
\caption{{\textbf{Characterization of Network Structures \text{under} the proposed utility Model}}}\label{summarytable2}
\vspace{0.1in}
\small
\begin {tabular} {||c||l||}
\hline
\hline
&\\
{\textbf{Pairwise stable networks}}  & {\textbf{Conditions}} \\
&\\
\hline
\hline
&\\
Complete network & $\delta > c$, $(\delta - c) \geq \delta^2 $ \\
&\\
\hline
& \\
Complete network & $\delta > c$, $(\delta - c) < \delta^2 $\\
Complete 2-partite network & \\
& \\
\hline
& \\
Complete network & $\delta = c$ \\
Shared network & \\
Null network & \\
Complete 2-partite network & \\
& \\
\hline
& \\
&$(\delta = c)$ and $a_i=a, \forall i \in K$ \\
Complete k-partite network & where $k \geq 3 \text{ and } a \in \{1,2,...\}$ \\
& \\
\hline
&\\
Null network & $(\delta < c)$\\
& \\
\hline
% $(\delta < c)$ and $ \displaystyle\frac{c-\delta}{\delta^2} \leq 2 $ & Shared network is pairwise stable. \\
% &\\
% \hli
Shared network & $(\delta < c)$ and $ 2 \geq \displaystyle\frac{c-\delta}{\delta^2} \geq 1 $  \\
& \\
\hline
& \\
Complete 2-partite network  & $(\delta < c)$ and $ \delta^2 \geq (c-\delta)$ \\
&\\
\hline
% &\\
% & $(\delta < c)$ and $a_i=a, \forall i \in K$ \\
% Complete k-partite network  & where $k \geq 3$ and $a \in \{1,2,...\}$ \\
% &\\
% \hline
&\\
& $(\delta - c) \leq \bigl(\frac{2}{3}\times \delta^2 \bigr)$, \\
Complete 3-partite network & $a_1=a_2=a_3=a$ \\
 & where $a \in \{1,2,...\}$   \\
&\\
\hline
\hline
\end {tabular}
% \end{minipage}
\end{table}
We summarize the pairwise-stability results in Table~\ref{summarytable2}. The proofs of the results not provided above follow is a similar way to the previously explained results and is not given here due to space constraints. 


\section{Simulation Results}\label{sec:Simulations}

In Section \ref{sec:Stability}, we remarked that studying the stability of standard networks is not such a bad idea. We now carry out simulations to capture the dynamics of network formation and compare the resultant pairwise-stable networks in such a dynamic process with the ones predicted theoretically.

\begin{figure*}[htb!]
\begin{tabular}{cccc}
\begin{minipage}{3.5 cm}
\centering
\includegraphics[scale=0.17, angle=-90]{Figures/std1} 
\end{minipage}
\hspace{0.1in}
&
\hspace{-0.2in}
\begin{minipage}{3.5 cm}
\centering
\includegraphics[scale=0.17, angle=-90]{Figures/std2} 
\end{minipage}
\hspace{0.1in}
&
\hspace{-0.2in}
\begin{minipage}{3.5 cm}
\centering
\includegraphics[scale=0.17, angle=-90]{Figures/std3}
\end{minipage}
\hspace{0.1in}
& 
\begin{minipage}{3.5 cm}
\centering
\includegraphics[scale=0.17, angle=-90]{Figures/std4}
\end{minipage}
\\
(a) & (b) & (c) & (d)
\end{tabular}
\caption{Regions of stability of some standard networks\label{fig:Expected-Regions-of-stability}}
\end{figure*}

\begin{figure*}[htb!]
\begin{tabular}{ccc}
\begin{minipage}{5.5 cm}
\centering
\includegraphics[scale=0.2, angle=-90]{Figures/fig1} 
\end{minipage}
&
\hspace{-0.2in}
\begin{minipage}{5.5 cm}
\centering
\includegraphics[scale=0.2, angle=-90]{Figures/fig2} 
\end{minipage}
&
\hspace{-0.2in}
\begin{minipage}{5.5 cm}
\centering
\includegraphics[scale=0.2, angle=-90]{Figures/fig3}
\end{minipage}
\\
(a) & (b) & (c)
\end{tabular}
\caption{Simulation Results for 10-actor networks\label{fig:Simulation-Results-N=00003D10}}
\end{figure*}

\subsection{Simulation Setup and Execution details}

We build a custom simulator using the C++~\cite{cplusplus} programming language. To implement the standard graph routines, we used the BOOST C++ libraries~\cite{boost}  which has efficient implementations of fundamental graph data structures and routines.

We model a social network as a graph, with actors represented by nodes and a relationship between two actors as an edge between corresponding nodes. We start with a random initial network consisting of $n$ actors. The number of relationships (edges) between these actors is determined by the parameter $density$. A density value of zero implies that we start with an empty network, a density value of 0.35 implies that we start with a network that already has 35\% of the $\binom{n}{2}$ edges. These edges are chosen uniformly randomly.

As noted in Section~\ref{utilitymodel}, for an actor, maintaining a direct edge with another actor  brings him a benefit of $\delta$ $(0<\delta\leq1)$ and costs him $c$ $(0<c\leq1)$. In addition, each actor reaps additional indirect benefit because of his potential to bridge his unconnected neighbors (determined by sparsity of relationships among his neighbors).

Each actor is given an opportunity to act, based on a random schedule. We have run simulations for a network with 10 actors. Each actor, when given an opportunity to act, considers all possible actions - namely, add an edge to an actor that he is not directly connected to, delete an existing edge to an actor, or do nothing. Each actor chooses the action that maximizes his individual payoff (as determined by the utility function described in Section~\ref{utilitymodel}). If addition or deletion of an edge does not change his individual utility, the actor prefers to do nothing. However, if both addition and deletion of an edge yields the same optimal utility, actors randomly choose one of these optimal choices. One iteration constitutes a situation when each actor in the network has been given exactly one opportunity to act. Note that actor $i$, when adding an edge to actor~$j$, is allowed to do so only if it is beneficial to both or if actor $j$ is at least not worse off. Similarly, actor $i$, when deleting an existing edge to actor $j$, is allowed to do so unilaterally.  

The network evolves dynamically as each actor chooses the action that maximizes his payoff. At some stage, the network could evolve into a stable state (equilibrium state) where no actor has any incentive to modify the network. One iteration in which no actor modifies the network is called an \textit{idle-iteration}, and the parameter \textit{Num-Idle-Terminate} ($=1$ in the simulations) indicates the number of idle-iterations before we conclude that the
network has reached a stable state. This is the case of normal termination of a simulation run.  There may be cases where the network does not emerge into a stable state and possibly cycles through  previously visited states even after many iterations (the case of \textit{dynamic-equilibrium} as noted in Hummon~\cite{hummon00}). The parameter \textit{Max-Iterations} ($=1000$  in the simulations) indicates the number of iterations before we forcibly terminate the simulation run. To average out results that are only due to chance and to improve the accuracy of simulation results, each simulation run is repeated \textit{Num-Repetitions}($=100$ in the simulations) times.

Once the network reaches a stable state, we classify the network structure as one of the following - \textit{Null, Star, Shared, Complete, Near-Null, Near-Star, Near-Shared, Near-Complete, k-partite, k-partite\: complete}. As in Hummon~\cite{hummon00}, we use the sorted (descending order) degree vector to characterize the structure of the stable network. For example, the Null network has a sorted degree vector of (0, 0, \ldots{}, 0), the Star network (n-1, 1, 1, \ldots{}, 1), the Shared network (2, 2, \ldots{}, 2), and the Complete network (n-1, n-1, \ldots{}, n-1). Also as in Hummon~\cite{hummon00}, we use total mean squared
deviation (MSD) to classify the resultant stable network as Near-\textquotedbl{}standard network\textquotedbl{} (for example, Near-complete network). 

%%%%%%%%%%%%%%%%%%%nrsuri comment begins

%%%%%%%%%%%%%%%%%%nrsuri comment ends

% The following example clarifies this procedure:Consider the 5-actor network in Figure \ref{fig:5-actor-network}. This network is a Complete network except for the 2 missing edges BE and DE. Therefore, we would like to classify this network as Near-Complete. This is done as follows. For this network, the sorted degree vector is (4, 4, 3, 3, 2). The total MSD of this network from Star network is 3.6 $=((4-4)^{2}+(4-1)^{2}+(3-1)^{2}+(3-1)^{2}+(2-1)^{2}))/5$. Similarly, the total MSD from Null network is 10.8, the total MSD from Shared network is 2, and the total MSD from the Complete Network is 1.2. The metric 1.2 being the least among these, we classify the above network structure as Near-Complete.

% \subsection{Metrics Recorded\label{sub:Metrics-Recorded}}
% 
% At the end of \textit{Num-Repetitions} number of repetitions, the following
% metrics were recorded.
% \begin{enumerate}
% \item The network structure (shape) for each repetition
% \item The frequency with which each of the network structures in Section
% \ref{sub:Classification-of-Network-Structures} resulted (across all
% repetitions)
% \item The mean utility of the final network (across all repetitions)
% \item The mean time to reach the final network (across all repetitions)
% \item The mean number of acts to reach the final network (across all repetitions)
% \end{enumerate}


\subsection{Simulation Results}

Based on the theoretical results provided in Table~\ref{summarytable2}, Figure \ref{fig:Expected-Regions-of-stability} shows the expected regions of stability for some standard networks as noted in Table~\ref{summarytable2}. The vertical axis of each sub-figure in Figure \ref{fig:Expected-Regions-of-stability} is the benefit value ($\delta$), ranging from 0.05 to 1, and the horizontal axis represents the cost parameter ($c$), ranging from 0.05 to 1. The region shade in blue shown the region in which the corresponding graph is stable.

Figure \ref{fig:Simulation-Results-N=00003D10} shows the simulation results for 10-actor networks. The vertical axis of each sub-figure in Figure \ref{fig:Simulation-Results-N=00003D10} is the benefit value ($\delta$), ranging from 0.05 to 1, and the horizontal axis represents the cost parameter ($c$), ranging from 0.05 to 1. As noted earlier, for a $<c,\delta>$ pair, we repeat the simulation for \textit{Num-Repetitions}. Each such repetition, could result in a network that can be classified as any of the structures as mentioned before. For purposes of these graphs, we plot the most frequent (modal) network structure as determined by the frequency with which each of the network structures resulted. The experiment was repeated starting from a empty graph and random graph with an edge density of $0.35$ and $0.70$.

We can note in Figure \ref{fig:Expected-Regions-of-stability} that there is an overlap of regions of stability of Null and Complete Bi-Partite networks. Looking at Figure~\ref{fig:Simulation-Results-N=00003D10}(b) and Figure~ \ref{fig:Simulation-Results-N=00003D10}(c), the Complete Bi-Partite network dominates the Null network (in the region of their overlap), because of the high density of number of edges in the initial network. Even though it is theoretically possible for a non-empty network to emerge in to an empty network, there is only one possible empty network, whereas, there are 10! (= 3628800)
Complete Bi-Partite graphs. Therefore, the likelihood of the Null network is rather small. However, when the density is zero (that it, we start with the empty network) as seen in column 1 in Figure \ref{fig:Simulation-Results-N=00003D10}, the Null network is the most probable network to emerge (because we are already in the Null network!) From Figure \ref{fig:Expected-Regions-of-stability}, there is an overlap of regions of stability of Shared and Complete bipartite networks. From Figure \ref{fig:Simulation-Results-N=00003D10}, we see that the Complete bipartite network dominates the Shared network. The Shared network is only a special instance of a Bi-Partite network. From Figure \ref{fig:Expected-Regions-of-stability}, there is an overlap of regions of stability of Complete and Complete Bi-Partite networks. From Figure \ref{fig:Simulation-Results-N=00003D10}, we see that the Complete Bi-Partite network dominates a major portion of this region of overlap, as, for a 10-actor network, there is only one Complete network, where as there are 3628800 Complete Bi-Partite graphs. However, as the density of the initial network increases, the likelihood of getting Complete network increases.

% Response: It may be difficult to conclude why all graphs are converging to complete.
% it basically depends on the structure as well as the number of edges in the initial network.
% I think right now we need not reason this to such detail.
%
%  \textbf{TODO: <Subbu and Rohith> According to this logic , the complete-bipartite
% network should totally totally dominate the Complete network in the
% region of overlap. What do you think is the reason why we don't see
% this behavior. Do you suspect anything wrong in the region of stability
% of the Complete equi-bipartite network as depicted in Figure \ref{fig:Expected-Regions-of-stability}?}
%

% Response: We are not adding for lower nodes. Higher nodes ( more than 10) are more interesting.
% \textbf{TODO: <We could add graphs for 3, 4, and 5 actor network also,
% if we are putting the paper in a journal>}

%The deviation of simulation results in Figure \ref{fig:Simulation-Results-N=00003D10}
%from the expected results in Figure \ref{fig:Expected-Regions-of-stability}
%could be attributed to the factor of network dynamics. Some aspects
%of network dynamics are - the state of the initial network before
%starting the simulation (i.e. the exact nature of pre-existing edges),
%the relative order in which each actor gets an opportunity to act
%(which determines the prevailing network structure when an actor gets
%to act), etc. The reader is referred to Hummon~\cite{hummon00}, for
%more details on the effects of network dynamics.

From the above we can see that the predicted structures do emerge in simulation and when there are
more than one graphs predicted, the outcome depends on the starting graph density and number of ways in which such a structure can emerge, i.e., the likelihood of that structure.


We also see that the graphs that emerge in simulation match one of the predicted stable graphs \footnote{(TODO: We need to identify exceptions if any, Srinath's results had all the experiments combined we will try to check only for MA-UD}




\section{Structure of Efficient Networks}\label{sec:Efficiency}

In this section, we study the structure of efficient networks, i.e., networks that maximize the
overall utility, under various conditions of $\delta$ and $c$. First, we begin by introducing some very useful classical results in Extremal Graph Theory which will be used later in our analysis. Please note that the terms \textit{graph} and \textit{network} are used interchangeably.

\subsection{Triangles in a Graph}
% We first give the definition of a \textit{Turan's graph}.
%\begin{definition}[Turan graph]
%Let $G=(V,E)$ be a simple graph with $n$ vertices and edge set $E$. Divide $V$ into $(p-1)$ pairwise disjoint subsets $V=V_1 \cup V_2 \cup \ldots \cup V_{p-1}$, $n_i = |V_i|$, $n = n_1+n_2+\ldots+n_{p-1}$. There is an edge joining two vertices if and only if the vertices lie in distinct sets $V_i, V_j$. We denote the resulting graph by $K_{n_1, \ldots, n_{p-1}}$; it has $\sum_{i<j} n_i n_j$ edges.
%We call $K_{n_1, \ldots, n_{p-1}}$ with $|n_i - n_j| \leq 1, \forall i, j \in \{1, \ldots, (p-1)\}$ as a \text{Turan graph}.
%\end{definition}
% \subsubsection{Triangles in Graph}

The number of triangles in a simple graph $G(V, E)$ plays a crucial
role in the utility computations of our network model and we state
here some classical results.  We know from Turan's theorem
~\cite{turan} it is possible to have a triangle free graph if the
following holds:

\begin{equation} \label{turantheorem} 
E \le \lfloor \frac{N^2}{4} \rfloor
\end{equation} 
Here $E$ denotes the number of edges and $N$ the number of vertices of 
the graph.  Moreover, from ~\cite{nor:ste}, we know that the number of triangles,
$T$, can be lower bounded, if the number of edges exceeds the
above value $\lfloor \frac{N^2}{4} \rfloor $, by

\begin{equation} \label{theorem2}
T \geq \frac{N(4E-N^2)}{9}
\end{equation}

%\begin{theorem}[\cite{turan}] \label{turantheorem}
%If a graph $G=(V,E)$ on $n$ vertices has no p-clique ($p\geq2$), then
%\begin{align}
%|E| &\leq \left(1- \displaystyle \frac{1}{p-1}\right) \displaystyle \frac{n^2}{2}
%\end{align}
%\end{theorem}
%When $p=3$, the theorem states that a triangle-free graph on $n$ vertices contains at most $\displaystyle \Bigl\lfloor\frac{n^2}{4} \Bigr\rfloor$ edges. This is the result which we will use in our analysis below.
%
%We also use the following lower bound on the number of triangles possible in simple graphs due to ~\cite{nor:ste}.

%\begin{theorem}[\cite{nor:ste}]\label{theorem2}
%Let \\ \text{$G=(V,E)$} be a simple graph of $n$ vertices. The number of triangles $T$ in the graph when  $ |E| > \left(\displaystyle \frac{N^2}{4}\right)$
%is lower bounded by,
%\begin{align} \label{lowerbound}
%T &\geq \frac{N(4E-N^2)}{9}
%\end{align}
%\end{theorem}
%Summarizing the above two results, we have that, in a graph with $E>\displaystyle\frac{N^2}{4}$, the minimum number of triangles possible is non-zero and is \textit{tightly} lower-bounded by Equation~\ref{lowerbound} whereas, the Turan's theorem states that when $E\leq \displaystyle\frac{N^2}{4}$, it is possible to have a triangle-free graph.

%An equiparitioned complete bi-partite graph (EBCG) is a complete bi-partite graph wherein the number of nodes in the two components differ at most by 1. We can easily see that the EBCG belongs to the class of \textit{Turan graphs} (when $p=3$) and it has at most $N^2 / 4 $ edges (equality holds when $N$ is even). Henceforth, we will refer to EBCG as the Turan graph (denoted by $G_{Turan}$).

In the discussion that follows we refer to a graph with no triangles and maximum number of edges as $G_{Turan}$, its easy to verify that such a graph is  a complete bi-partite graph, and the the number of vertices in each partition differs at most by 1. Call this {\bf EBCG}, Equi-Bi-Partite Complete Graph.
% \subsection{ $\delta = c $ }
% Here we show that a Turan's graph maximizes the utility. Turan's graph
% also maximizes $\sum {d_i} $ and thus the total number of edges.
% It is a bi-partite graph thus the second term is $1$, as the number of
% connected neighbours is nil.



\subsection{Finding the efficient graph}

\begin{definition}[Efficiency]

The efficiency of a given network $G$(denoted by $u(G)$) is taken to be the sum
of utilities of all the actors (nodes) in that network. Its given by

\begin{align}
u(G) &= \sum_{i=1}^{N} u_{i}
\end{align}
\end{definition}

Individual utilities ($u_i, \forall i$) are defined as in
Equation~\ref{utilitymodel}.  We now present the results on the efficient graph
topologies in the network with the prescribed utility model under various
conditions on $\delta$ and $c$ parameters.

%As explained earlier, we can see the utility of a
%node has two components, one the utility from all its direct connections and a
%indirect utility due to the information flow among the dis-connected
%neighbours.

\begin{theorem}
When $ \delta > c $ and $ (\delta - c ) > \delta^2$ , the complete graph is the unique efficient graph in LNFG .
\end{theorem}
\begin{proof}
For sufficiently large $N$, the gain from direct links exceeds the bridging
benefits for all the nodes in the network, resulting in a complete graph.
\end{proof}

\begin{theorem}
When $ \delta <  c $ and $\delta^2 < (c - \delta)$, the Null graph is the unique efficient graph in LNFG.
\end{theorem}
\begin{proof}
For any node $d_{i} > 0 $ implies the utility of that node is negative thus
reduces the over all network utility.  This follows from $(\delta - c + \delta^{2}) $
being negative.
\end{proof}

\begin{theorem}
When $ \delta = c $, the Turan graph is the unique efficient graph in LNFG.
\end{theorem}

\begin{proof}
We will analyze the efficiency of a arbitrary graph (denoted by $G$) as follows.
\begin{align}\label{efficiency_equation}
\nonumber u(G) &= \sum_{i=1}^{N} u_{i} = \sum_{i=1}^{N} d_{i} \delta^{2} \left( 1 - \displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right ) \\
\nonumber &= \delta^{2} \sum_{i=1}^{N} d_{i} - \delta^{2} \sum_{i=1}^{N}
                 \displaystyle\frac{2 \sigma_{i}}{(d_{i} - 1)} \\
\nonumber & \le \delta^{2} \sum_{i=1}^{N} d_{i} - \frac{\delta^{2}}{(N-2)}
            \sum_{i=1}^{N} 2 \sigma_{i} \\
&=  \delta^{2} \sum_{i=1}^{N} d_{i} - \frac{\delta^{2}}{(N-2)} (2 \times 3 \times T_{3}(G))
\end{align}
where, $T_{3}(G) $ is the number of triangles is the graph $G$. The last step
of the above simplification emerges from the fact that the number of links
among the neighbours of a node $i$ is the number of triangles in the graph in
which node $i$ is one of the vertices of the triangle. The factor $3$ in the
last step is due to the fact that every triangle contributes to the
$\sigma_{i}$ of $3$ nodes. We know that, for an efficient graph, equation
~\ref{efficiency_equation} should be maximized and that happens when the
number of triangles in a graph is minimized while simultaneously  maximizing
the number of edges in the graph.

Turan graph (refer equation ~\ref{turantheorem}) is a graph with maximum edges
that has no triangles.  So an efficient graph must have an efficiency greater
than or equal to that of a Turan graph. Thus, it is clear that there is no need to
consider graphs with edges lesser than that of a Turan graph.

%We also know from
%Theorem~\ref{turantheorem} that it is a triangle free graph with the maximal
%number of edges. It is clear just deleting edges from the Turan graph will only
%reduce the efficiency of the resultant graph when compared with the efficiency
%of the Turan graph. This is because deleting edges will reduce the utility got
%due to direct links and in addition, may introduce new triangles in the graphs
%which reduces the utility due to indirect links. So, there cannot be any graph
%with fewer edges than the Turan graph which yields a better efficiency value
%than Turan graph.

Let us consider the case when a graph (denoted by $\overline{G}$) has more edges than the Turan graph.
\textit{Does this graph have better efficiency?} 
Let $\overline{G}$ have $\lceil N^2/4 \rceil +  x$ edges where $x>0$.

From Equation~\ref{efficiency_equation}, we know that
\begin{align}\label{eqn5.5}
\nonumber u(\overline{G}) &= \delta^{2} \displaystyle\sum_{i=1}^{N} d_{i} - \delta^{2} \displaystyle\sum_{i=1}^{N} \frac{2 \sigma_{i}}{(d_{i} - 1)} \\
&\le \delta^{2} \left(2 \left(\frac{n^2}{4} +x\right)\right) - \frac{\delta^{2}}{(N-2)} (6 T_{3}(\overline{G}))
\end{align}
where $T_{3}(\overline{G})$ is the number of triangles in $\overline{G}$.

From Equation ~\ref{theorem2}, we have
\begin{align}\label{eff_g_dash}
u(\overline{G}) & \le \delta^{2} \left(2\left(\frac{n^2}{4} +x\right)\right) - \frac{\delta^{2}}{(N-2)} \left(6 N \left(\frac{4E-N^2}{9}\right) \right)
\end{align}
Since $T_3(G_{Turan}) = 0$, the efficiency of the Turan graph is given below.
\begin{align}
u(G_{Turan}) = \sum_{i} u_i&=\delta^{2} \left(2\times \frac{n^2}{4}\right)
\end{align}

The change in efficiency ($\Delta{u}$) between the two graphs is given by
\begin{equation}
\label{deltagain}
\Delta{u} = u(\overline{G}) - u(G_{Turan}) \le 2 \delta^2 \left (x  - \frac{N}{(N-2)} \frac{4x}{3} \right)
\end{equation}
which is clearly negative for $x>0$.  The net increase in overall network utility is negative, for all $ x > 0 $, thus proving that Turan graph (i.e., the EBCG) is the unique efficient graph.
\end{proof}

%\textit{Note:} In Equation~\ref{eqn5.5}, the inequality for $u(\overline{G})$ is strict as $d_i$ is replaced with (N-1) $\forall i$. This is possible only for a complete graph with sparsity $0$. Thus the $\Delta u$ in Equation~\ref{deltagain} is a strict inequality, and we also know if we reduce the number of edges we can achieve triangle free graphs but they too have a utility strictly less than the Turan graph. Thus we can conclude the Turan graph is the \textit{unique} graph with maximum utility (up to an isomorphism of the labels of the nodes).

% \subsection{Case: $ \delta < c $ and $ \delta^2 > (c - \delta) $}
\begin{theorem}
When $ \delta < c $ and $ \delta^2 > (c - \delta) $, the Turan graph is the unique efficient graph in LNFG.
\end{theorem}
\begin{proof}
We will see that Turan's graph is the efficient graph in this
case too. We will prove this by contradiction. Suppose there is another
graph (denoted by $\overline{G}$) that is the efficient graph. Since $ \delta < c $ and $ \delta^2 > (c - \delta) $, in the expression for efficiency (given in the equation below), the benefit from direct links is negative but the benefit from sparsity of the neighbours can compensate this negative term to take the overall utility to a positive quantity. Since $\overline{G}$ is the efficient graph, it has to be that the term due to sparsity has to be greater than the corresponding value for the Turan graph which implies,

\begin{align}\label{efficiency_equation1}
\nonumber u(\overline{G}) &= \sum_{i=1}^{N} u_{i} = \underbrace{(\delta-c)\sum_{i=1}^{N} d_i}_{\text{negative}} + \underbrace{\sum_{i=1}^{N} d_{i} \delta^{2} \left( 1 - \displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right )}_{\text{utility more than } G_{Turan}} \\
\end{align}

This implies that we this graph would give a higher utility for the $\delta = c$ ~case, as the first term is $0$ there.
This contradicts our previous result, so our assumption that Turan graph is inefficient must be wrong.
\end{proof}

% \newpage
% \subsection{ CASE: $ \delta > c $ and $\delta^2 > 3(\delta - c) $ }

\begin{table}[h]
\caption{{\textbf{Characterization of Efficient Network Structures in LNFG}}}\label{summarytable3}
\vspace{0.1in}
\centering
\begin {tabular} {||l||l||}
\hline
\hline
%&\\
{\textbf{Parameter Range}} & {\textbf{Efficient Topologies}} \\
%&\\
\hline
%&\\
$ \delta <  c $ and $\delta^2 < (c - \delta)$ & Null network \\ 
%&\\
\hline
%&\\
$ \delta < c $ and $ \delta^2 > (c - \delta) $  & Turan network \\
%&\\
\hline
$ \delta = c $ & Turan network \\
%&\\
\hline
$ \delta > c $ and $\delta^2 > 3(\delta - c) $ & Turan network \\
%&\\
\hline
$ \delta > c $ and $ (\delta - c) < \delta^2 < 3(\delta - c) $ & Turan network \\ 
&  (CONJECTURE)  \\
%&\\
\hline
%&\\
$ \delta > c $ and $ (\delta - c ) > \delta^2$ & Complete network  \\
%&\\
%\hline
%                                         & Turan network \\
%$ \delta < c $ and $(c-\delta) = \delta^2$ & Null network \\
%&\\
\hline
\hline
\end {tabular}
\end{table}

\begin{theorem}
When $ \delta > c $ and $\delta^2 \geq 3(\delta - c) $, the Turan graph is the unique efficient graph in LNFG.
\end{theorem}
\begin{proof}
Let $\overline{G}$ be the efficient graph. Using similar analysis to Equation~\ref{eff_g_dash}, we can see that
\begin{multline}\label{eff_g_dash1}
\nonumber u(\overline{G}) \le (\delta+c+\delta^{2}) \left(2\left(\displaystyle\frac{n^2}{4} +x\right)\right) - \\ \frac{\delta^{2}}{(N-2)} \left(6 N \left( \frac{4E-N^2}{9}\right)\right) \\
= (\delta+c+\delta^{2}) \left(2 \left(\displaystyle\frac{n^2}{4} +x\right)\right) - \frac{\delta^{2}N}{(N-2)} \left(\frac{8x}{3}\right)
\end{multline}
For the Turan graph (or the EBCG), it can also be seen by simple analysis that
\begin{align}
\nonumber u(G_{Turan}) &= \displaystyle\frac{N^2}{2} \left( \delta-c+\delta^2 \right) \\
\nonumber \Rightarrow u(\overline{G})-u(G_{Turan}) & \le 2x\left( (\delta-c+\delta^2) - \displaystyle \frac{4N\delta^2} {3(N-2)} \right) \\
 & < 2x\left( (\delta-c+ \delta^2) - \displaystyle \frac{4\delta^2}{3} \right)
\end{align}
% For sufficiently large $N$ such that $\displaystyle \frac{N}{N-2} \approx 1$, we can see that
% \begin{align}
% \end{align}
Thus, when $\delta^2 \geq 3(\delta-c)$, the Turan graph is the unique efficient graph.
\end{proof}

% TO BE CHECKED WITH SUBBU
% This follows from the equation \ref{deltagain}. That equation can be
% made to go to a near zero only if the benefit from
% the direct links increases by  $ \frac{2}{3} x \delta^2 $.

% \subsection { $ \delta > c $ and $ (delta - c) < \delta^2 < 3(\delta - c) $ }
\begin{conjecture}\label{conj1}
When $ \delta > c $ and $ (\delta - c) \leq \delta^2 < 3(\delta - c) $, the Turan graph is the efficient graph under the utility model of Equation~\ref{utilitymodel}.
\end{conjecture}

We summarize the efficiency results in Table~\ref{summarytable3}.

%\textbf{Remark: } It can be shown (through some algebraic simplification) that the completely connected k-partite graph is less efficient than the EBCG. But, since this does not show that the EBCG is the efficient graph, we are not including the detailed proof here.
% \textbf{<TODO: We can show the above  result for any completely connected k-partite graph. ???>}




\section{Price of stability}\label{POS}

\begin{definition}[Price of stability]
Price of stability ($PoS$) is defined as follows.
\begin{align}
\nonumber PoS & = \displaystyle \frac{\text{Best Pairwise Stable Network}}{\text{Efficient Network}}
\end{align}
\end{definition}

We now evaluate the $PoS$ values under various conditions of the parameters $\delta$ and $c$.

\begin{theorem}
The Price of Stability (PoS) values in LNFG are as follows:
\begin {enumerate}
\item When $ \delta > c $ and $ (\delta - c ) > \delta^2$, \textit{PoS= 1}
\item  When $ \delta > c $, $\delta^2 > (\delta - c) $ and $\delta^2 \geq 3(\delta - c) $, \textit{PoS= 1}
\item When $ \delta = c $, \textit{PoS = 1}
\item When $ \delta < c $ and $ \delta^2 > (c - \delta) $,  \textit{PoS=  1}
\item When $ \delta < c $ and $ \delta^2 < (c - \delta) $,   \textit{PoS is undefined}
\end {enumerate}
\end{theorem}
\begin{proof}
The results are easily obtained by referring to Table~\ref{summarytable2} and Table~\ref{summarytable3}.
\end{proof}

In view of Conjecture~\ref{conj1}, we have the following result about the $PoS$ when $ \delta > c $  and $ (\delta - c) \leq \delta^2 < 3(\delta - c) $.

\begin{theorem}
When $ \delta > c $ and $ (\delta - c) \leq \delta^2 < 3(\delta - c) $, the Price of Stability (PoS) is always greater than  $\frac{1}{2}$ in LNFG. 
\end{theorem}
\begin{proof}
We know that, under the conditions $ \delta > c $ and $ (\delta - c) <\delta^2 < 3(\delta - c) $, the best pairwise stable graph is the Turan graph (as seen from Table~\ref{summarytable2})
%or the complete graph. If  Conjecture~\ref{conj1} is true, then the Turan graph is the efficient as well as the best pairwise stable network. Hence, $PoS = 1 > \frac{1}{2}$. 
Let Conjecture~\ref{conj1} be false.
% Now, the best pairwise stable graph can be either the Turan graph or the complete graph.
In this scenario, let us denote the efficient graph by $\overline{G}$. We will now evaluate an upper bound on the  maximum efficiency of $\overline{G}$. We know that $\overline{G}$  has to have more direct links as $\delta > c $ than the Turan graph to be a candidate for the most efficient graph. Let $\overline{G}$ have $\left(\displaystyle\frac{N^2}{4} + x\right)$ edges where $x>0$.

\begin{align}\label{efficiency_equation2}
\nonumber u(\overline{G}) = \sum_{i=1}^{N} u_{i} = (\delta-c)\sum_{i=1}^{N} d_i+ \sum_{i=1}^{N} d_{i} \delta^{2} \left( 1 - \displaystyle\frac{\sigma_{i}}{\binom{d_{i}}{2}} \right ) \\
\nonumber = (\delta-c+\delta^{2})\sum_{i=1}^{N} d_i - \delta^{2}\left(\displaystyle\frac{2\sigma_{i}}{d_i-1} \right )
\end{align}
Since  $d_i$ can be at most $(N-1)$,
\begin{align}
\nonumber u(\overline{G}) \leq (\delta-c+\delta^{2}) N(N-1) - \left(\frac{2\delta^{2}}{N-2}\right) \sum_{i=1}^{n}  \sigma_i \\
\nonumber u(\overline{G}) \leq (\delta-c+\delta^{2}) N(N-1) - \left(\frac{2\delta^{2}}{N-2}\right) T_3(\overline{G})
\end{align}
By Theorem~\ref{theorem2}, we have 
\begin{align}
\nonumber u(\overline{G}) &\leq  (\delta-c+\delta^{2}) N(N-1) - \left(\frac{2\delta^{2}}{N-2}\right) \left(\displaystyle \frac {N(4E-N^2)}{9}\right) \\
\nonumber &= (\delta-c+\delta^{2}) N(N-1) - \left(\frac{\delta^{2}N}{N-2}\right) \left(\displaystyle \frac {8x}{9}\right)
\end{align}
Since $\displaystyle\left(\frac{\delta^{2}N}{N-2}\right) \left(\displaystyle \frac {8x}{9}\right) > 0$, we have 
\begin{align}
\nonumber u(\overline{G}) \leq  (\delta-c+\delta^{2}) N(N-1) 
\end{align}
% If the Turan graph is the best pairwise stable graph, then we have 
Turan graph is a pair wise stable graph under these conditions [Table~\ref{summarytable2}], and
$ u(G_{Turan}) = (\delta-c+\delta^2) \left(\displaystyle\frac{N^2}{2}\right) $
\begin{align}
\nonumber PoS & \ge \frac{u(G_{Turan})}{u(\overline{G})} \geq \displaystyle \frac{(\delta-c+\delta^2) \left(\displaystyle\frac{N^2}{2}\right)}{(\delta-c+\delta^{2}) N(N-1) } \\ 
\nonumber PoS & \geq \displaystyle \frac{N}{2(N-1)}
\end{align}
Thus, we conclude, $ PoS > \frac{1}{2}  $
\end{proof}
%\begin{align}\label{eqn1}

%%%%%%%%%%%%%%%%%%%%nrsuri commented
%\begin{center}
%\begin{table}
%\label{eqn1}
%\begin{tabular}{l l}
%$\nonumber u(G_{Turan})$ & $= (\delta-c+\delta^2) \left(\displaystyle\frac{N^2}{2}\right)$ \\
%$\nonumber \Rightarrow PoS$ &= $\displaystyle \frac{u(G_{Turan})}{u(\overline{G})}$ \\
%$\nonumber \Rightarrow PoS$ & $\geq \displaystyle \frac{(\delta-c+\delta^2) \left(\displaystyle\frac{N^2}{2}\right)}{(\delta-c+\delta^{2}) N(N-1) } $\\
%$\nonumber \Rightarrow PoS $ & $\geq \displaystyle \frac{N}{2(N-1)} $\\
%$\Rightarrow PoS$ & $> \displaystyle \frac{1}{2}$
%\end{tabular}
%\end{table}
%\end{center}
%%%%%%%%%%%%%%%%%%%%nrsuri commented

%\end{align}

% If the complete graph is the best pairwise stable graph, then
% \begin{align}\label{eqn2}
% \nonumber u(G_{complete}) &= (\delta-c) N (N-1)\\
% \nonumber \Rightarrow PoS &= \displaystyle \frac{u(G_{complete})}{u(\overline{G})} \\
% \nonumber \Rightarrow PoS &\geq \displaystyle \frac{(\delta-c) \left(N(N-1)\right)}{(\delta-c+\delta^{2}) N(N-1) } \\
% \nonumber \Rightarrow PoS &\geq \displaystyle \frac{1}{1+\left(\frac{\delta^2}{(\delta-c)}\right)}
% \end{align}
% From hypothesis, we know that $1 < \frac{\delta^2}{\delta-c}< 3$
% \begin{align}
% \Rightarrow PoS &>\displaystyle\frac{1}{4}
% \end{align}
%
% From Equation~\ref{eqn1} and Equation~\ref{eqn2}, we have
% \begin{align}
% \Rightarrow PoS &> \displaystyle\frac{1}{4}
% \end{align}

\section{Conclusions and Future Work}\label{conclusion}
In this paper, we examined the local network formation game (i.e., LNFG) when a set of rational and intelligent agents wish to form links among themselves for the purpose of routing information or traffic. We particularly examine the scenario when utility of each agent depends only on the local information in the network (or the neighborhood of the agent). In such scenarios, in general, the set of equilibrium network topologies may appear quite different from the topologies of centrally enforced optimum (or efficient) networks. Using the proposed LNFG, we characterized topologies of equilibrium networks and topologies of efficient networks based on a few classical results from extremal graph theory. Then we studied the price of stability in LNFG  in order to reveal the compatibility of equilibrium networks versus efficient networks. Interestingly, we find that price of stability is 1 for almost all values of the parameters in LNFG. Only for a few values of the parameters in LNFG, we obtained a lower bound of 1 on price of stability. This indicates 
that, under mild conditions, the proposed LNFG produces equilibrium networks that are efficient as well. Moreover, we have experimentally studied the dynamics of LNFG thus validating the analytical predictions of the topologies of equilibrium networks using LNFG. 

With respect to future work, additional studies on price of anarchy can be carried out in LNFG which can yield better insights in the network formation process. Also, there is a need to examine the scenario when we consider directed networks instead of undirected networks as examined in the paper. We can additionally incorporate the sociological concept of homophily that is usually observed in social networks in our model and examine the tradeoffs between equilibrium and efficient networks in this enhanced setting. 

% \section*{ACKNOWLEDGEMENTS}
% We thank Gregoire Seux who was involved in some very useful discussions during the initial stages of this paper. 

\begin{thebibliography}{[MT1]}

\bibitem{anshelevich:03}
E.~Anshelevich, A.~Dasgupta, E.~Tardos, and T.~Wexler. \newblock
{\em Near-Optimal Network Design with Selfish Agents}.
\newblock In Proceedings of 25th Annual ACM Symposium on Theory of Computing
(STOC), pages 511-520, 2003.

\bibitem{anshelevich:08}
E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler,
and T. Roughgarden. \newblock {\em The Price of Stability for
Network Design with Fair Cost Allocation}. \newblock SIAM Journal
on Computing, 38(4):1602-1623, 2008.

\bibitem{aumann:88}
R.J. Aumann and R.B. Myerson.
\newblock {\em Endogenous Formation of Links Between
Players and Coalitions: An Application of the Shapley Value}.
\newblock In: A.E. Roth (editor). The Shapley Value,
Cambridge University Press, pages 175-191, 1988.

\bibitem{bala:00}
V.~Bala and S.~Goyal. \newblock {\em A Non-Cooperative Model of
Network Formation}. \newblock Econometrica, 68: 1181-1229, 2000.

\bibitem{buskens-vanderijt:07}
V.~Buskens and A.~van~de Rijt.
\newblock Dynamics of networks if everyone strives for structural holes.
\newblock {\em American Journal of Sociology}, 114(2):371--407, 2008.

\bibitem{corbo:05}
J.~Corbo and D. Parkes.
\newblock {\em The Price of Selfish Behavior in Bilateral Network
Formation}.
\newblock In Proceedings of the 24th Annual ACM symposium on Principles of Distributed
Computing (PODC), pages 99-107, 2005.

\bibitem{doreian06}
P. Doreian.
\newblock Actor network utilities and network evolution.
\newblock {\em Social Networks}, 28:137--164, 2006.

\bibitem{fabrikant:03}
A.~Fabrikant, A.~Luthra, E.~Maneva, C.~Papadamitriou, and
S.~Shenker. \newblock {\em On a Network Creation Game}. \newblock
In Proceedings of the 22th Annual ACM symposium on Principles of
Distributed Computing (PODC), pages 347-351, 2003.

\bibitem{galeotti:06}
A.~Galeotti, S.~Goyal, J.~Kamphorst.
\newblock {\em Network formation with heterogeneous players}.
\newblock {\em Games and Economic Behavior}, 54(2):353-372, 2006.

\bibitem{goyal:07}
S.~Goyal.
\newblock {\em Connections: An Introduction to the Economics of Networks}.
\newblock Princeton University Press, Princeton and Oxford, 2007.

\bibitem{goyal-vegaredondo:07}
S.~Goyal and F.~Vega-Redondo.
\newblock Structural holes in social networks.
\newblock {\em Journal of Economic Thoery}, 137(1):460--492, 2007.

\bibitem{haller:03}
H. Haller and S. Sarangi. \newblock {\em Nash Networks with
Heterogeneous Agents}. \newblock LSU Working Paper 2003-06, 2003.

\bibitem{hummon00}
N.P. Hummon.
\newblock Utility and dynamic social networks.
\newblock {\em Social Networks}, 22:221-249, 2000.

\bibitem{jackson-wolinsky:96}
M.~O. Jackson and A.~Wolinsky.
\newblock A strategic model of social and economic networks.
\newblock {\em Journal of Economic Theory}, 71(1):44-74, 1996.

\bibitem{jackson:02}
M.~O. Jackson and A.~Watts.
\newblock The Evolution of Social and Economic Networks.
\newblock {\em Journal of Economic Theory}, 106(2):265-295, 2002.

\bibitem{jackson:04}
M.O. Jackson.
\newblock {\em A Survey of Models of Network Formation: Stability and Efficiency}.
\newblock In G. Demange and M. Wooders (editors). Group Formation in Economics; Networks, Clubs and Coalitions.
Cambridge University Press, Cambridge, U.K., 2004.

\bibitem{jackson:08}
M.~O. Jackson.
\newblock {\em Social and Economic Networks}.
\newblock Princeton University Press, Princeton and Oxford, 2008.

\bibitem{johnson:00}
C.~Johnson and R.P.~Gilles.
\newblock {\em Spatial social networks}.
\newblock {\em Review of Economic Design}, 5(3):273-299, 2000.

\bibitem{kstw:08}
J.~Kleinberg, S.~Suri, E.~Tardos, and T.~Wexler. Strategic network
formation with structural holes. In Proceedings of the 9th ACM
Conference on Electronic Commerce (EC), pages 284-293, 2008.

\bibitem{lopez:04}
D. Lopez-Pintado. \newblock {\em A cost-sharing model of network
formation: Anti-coordination games}. \newblock International
Journal of Game Theory, 33(1):1-19, 2004.

\bibitem{melendez:02}
M.A. Melendez-Jimenez. \newblock {\em Network Formation and
Coordination: Bargaining the Division of Link Costs}.
\newblock In Proceedings of the 5th Spanish Meeting on Game Theory and
Applications, 2002.

\bibitem{myerson:91}
R.B. Myerson.
\newblock {\em Game Theory: Analysis of Conflict}.
\newblock Harvard University Press, Cambridge, USA, 1991.

\bibitem{nor:ste}
E.A. Nordhaus, B.M. Stewart. \newblock {\em Triangles in Ordinary
Graph}. \newblock Canadian Journal of Mathematics, 15(1):33-41,
1963.

\bibitem{sarangi:03}
S. Sarangi, R. Kannan, and L. Ray. \newblock {\em The Structure of
Information Networks}. \newblock Royal Economic Society Annual
Conference, 2003.

% ADDED ROHITH 
\bibitem{jackson:2003}
Matthew O. Jackson. {\em A Survey of Models of Network Formation: Stability and Efficiency}.
Technical Report, California Institute of Technology,  March 2003.

\bibitem{turan}
Turan, Paul. {\em On an extremal problem in graph theory}. Matematikai es Fizikai Lapok (436-452), 1941.

\bibitem{boost}
{\em Boost C++ Libraries}. http://www.boost.org/

\bibitem{cplusplus}
{\em The C++ Programming Language}. http://en.wikipedia.org/wiki/C\%2B\%2B


\end{thebibliography}

\end{document}
